/**
 * Copyright 2009 Takahiko Ito
 * 
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); 
 * you may not use this file except in compliance with the License. 
 * You may obtain a copy of the License at 
 * 
 *    http://www.apache.org/licenses/LICENSE-2.0 
 *        
 * Unless required by applicable law or agreed to in writing, software 
 * distributed under the License is distributed on an "AS IS" BASIS, 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
 * See the License for the specific language governing permissions and 
 * limitations under the License.
 */
package org.unigram.oluolu.rqe.selector;

import org.apache.hadoop.conf.Configuration;

/**
 * Validate the query pair is related or not by the value of edit 
 * distance value. When the value is lower than the threshold the 
 * queries should be related. Otherwise they are not related. 
 */
public class LevenshteinSelector implements ISelector {
    
    /**
     * Validate the query pair is related each other.
     *
     * @param firstQuery query string
     * @param secondQuery query string compared with firstQuery
     * @return true when the levenshetein value is lower than 
     *          the threshold otherwise return false.
     */
    public final boolean run(final String firstQuery, 
            final String secondQuery) {
        
        /* preliminary checking by their length */
        if (firstQuery.length() == 0 || secondQuery.length() == 0 
                || (Math.abs(firstQuery.length() 
                        - secondQuery.length()) > this.lengthDiffThreshold)) { 
            return false;
        } 

        /* calc edit distance */
        int[][] d = new int[firstQuery.length() + 1][secondQuery.length() + 1];
        for (int i = 0; i <= firstQuery.length(); i++) {
            d[i][0] = i; // deletion 
        }
        for (int j = 0; j <= secondQuery.length(); j++) {
            d[0][j] = j; // insertion
        }
        for (int j = 0; j < secondQuery.length(); j++) {
            for (int i = 0; i < firstQuery.length(); i++) {
                if (firstQuery.charAt(i) == secondQuery.charAt(j)) {
                    d[i + 1][j + 1] = d[i][j];
                } else {
                    d[i + 1][j + 1] = Math
                            .min(d[i][j + 1] + 1, d[i + 1][j] + 1);
                    d[i + 1][j + 1] = Math.min(d[i + 1][j + 1], d[i][j] + 1);
                }
            }
        }
        
        if (d[firstQuery.length()][secondQuery.length()] 
                                   < levenshteinThreshold) {
            return true;
        } 
        return false;
        
    }

    /**
     * Constructor.
     *
     * @param jc extract threshold assigned by users.
     */
    public LevenshteinSelector(final Configuration jc) {
        levenshteinThreshold = jc.getLong(RQE_LEVENSHTEIN_THRESHOLD,
                DEFAULT_RQE_LEVENSHTEIN_THRESHOLD);
        lengthDiffThreshold = jc.getLong(RQE_LENGTH_DIFF_THRESHOLD,
                DEFAULT_RQE_LENGTH_DIFF_THRESHOLD);
     }
    
    /** symbol: levenshtein threshold. */
    public static final String RQE_LEVENSHTEIN_THRESHOLD
        = "oluolu.rqe.levenshtein.threshold";
    
    /** default: threshold for levenshtein distance. */
    public static final long DEFAULT_RQE_LEVENSHTEIN_THRESHOLD = 3;    

    /** symbol: length difference threshold. */
    public static final String RQE_LENGTH_DIFF_THRESHOLD
        = "oluolu.rqe.length.diff.threshold";
    
    /** default: threshold for length difference. */
    public static final int DEFAULT_RQE_LENGTH_DIFF_THRESHOLD = 3;    
 
    /** edit distance threshold. */
    private long levenshteinThreshold;
    
    /** length difference threshold. */
    private long lengthDiffThreshold;    
    
}